// https://leetcode-cn.com/problems/linked-list-cycle-ii/
// 142. 环行链表 II
// 给定一个链表的头节点 head，返回链表开始入环的第一个节点。如果链表无环，
// 则返回 null
import { ListNode } from '../utils/index.ts';

function detectCycle(head: ListNode | null): ListNode | null {
    if (head === null) return null;
    let fast: ListNode | null = head;
    let slow: ListNode | null = head;
    while (fast !== null) {
        slow = slow && slow.next;
        if (fast.next !== null) {
            fast = fast.next.next;
        } else {
            return null;
        }

        if (slow === fast) {
            let ptr: ListNode | null = head;
            while (slow !== ptr) {
                ptr = ptr && ptr.next;
                slow = slow && slow.next;
            }
            return ptr;
        }
    }

    return null;
}
